| Algorithm Deep Dives |
|---|
| 1. Z Algorithm |
| 2. Manacher’s Algorithm |
| 3. Gosper’s Hack Algorithm |
This post introduces Manacher’s algorithm.
What is Manacher’s Algorithm?
Manacher’s algorithm was invented by Glenn K. Manacher and is used to find the longest palindromic substring in a string. It runs in linear time with complexity O(N).
A palindrome is a string that reads the same forward and backward; for example, “radar”, “level”, “noon”, and “civic”.
We will build up to it step by step and optimize the code along the way.
Implementation
Brute-Force
We start with a brute-force approach.
Three nested loops check every substring between pointers i and j to see if it is a palindrome.
fun bruteForce(str: String): String {
var maxLength = 1
var start = 0
// Check whether the substring between pointers i and j is a palindrome.
for (i in str.indices) {
for (j in i until str.length) {
// Length of the substring to check (distance between i and j).
val range = j - i + 1
var isPalindrome = true
// A palindrome is checked from both ends, so we only iterate over half the range.
for (k in 0 until range / 2) {
// If the characters at both ends differ, it is not a palindrome; stop early.
if (str[i + k] != str[j - k]) {
isPalindrome = false
break
}
}
// If it is a palindrome and longer than the current best, update the answer.
if (isPalindrome && range > maxLength) {
start = i
maxLength = range
}
}
}
return str.substring(start, start + maxLength)
}
With three for loops, the time complexity is O(N^3).
Dynamic Programming
That is too slow. We use dynamic programming: store results of subproblems and reuse them to reduce time complexity.
A Boolean table stores whether each substring is a palindrome so we can use previous results to decide.
fun dp(str: String): String {
val len = str.length
// An n x n Boolean table that stores whether each substring is a palindrome.
val table = Array(len) { BooleanArray(len) }
// Every single character is a palindrome of length 1.
for (i in str.indices) {
table[i][i] = true
}
var start = 0
var maxLength = 1
// Even-length palindromes start from length 2. For faster searching, pre-check palindromes of length 2.
// Odd-length palindromes are already covered by the length-1 initialization above.
for (i in 0 until len - 1) {
if (str[i] == str[i + 1]) {
table[i][i + 1] = true
start = i
maxLength = 2
}
}
// Since we already checked length-1 and length-2 palindromes, we only need to check length >= 3 here.
for (i in 3..len) {
// A palindrome is checked from both ends.
for (j in 0 until len - i + 1) {
val range = j + i - 1
// table[j + 1][range - 1] indicates whether the inner substring is a palindrome.
// For example, when checking "abba", we do not need to re-validate the inner "bb" if it was already computed.
// If the inner substring is a palindrome, the current substring can be a palindrome as well; check the ends and store the result.
// In the next iterations, we can reuse this stored result.
if (table[j + 1][range - 1] && str[j] == str[range]) {
table[j][range] = true
if (i > maxLength) {
start = j
maxLength = i
}
}
}
}
return str.substring(start, start + maxLength)
}
With two nested loops, the time complexity is O(N^2).
Manacher’s Algorithm
How does Manacher’s algorithm solve this?
Like the DP approach, we can use previously computed results to validate the next palindrome.
In the DP solution we always had to handle length-2 palindromes for even-length cases, but for odd lengths we did not. So if we assume the string has odd length, we can skip even lengths and only consider odd-length palindromes.
We scan from the left, find the longest palindrome at each step, and store the rightmost end of the current palindrome. We then use the symmetric position to validate new palindromes.
The implementation below explains the details.
fun manachersAlgorithm(str: String): String {
// We insert separators and sentinels, so the length becomes str.length * 2 + 3.
val length = str.length * 2 + 3
val charArray = CharArray(length)
// Add sentinels at both ends to avoid bounds checks at the edges.
charArray[0] = '^'
charArray[charArray.lastIndex] = '$'
var p = 1
// Manacher's algorithm works on odd-length strings, so insert '#' between characters to make all palindromes odd-length.
for (c in str) {
charArray[p++] = '#'
charArray[p++] = c
}
charArray[p] = '#'
var maxLength = 0
var start = 0
var center = 0
var maxRight = 0
val table = IntArray(length)
for (i in 1 until length - 1) {
// If i is within the current rightmost palindrome, we can reuse information via symmetry.
if (i < maxRight) {
// Compare (maxRight - i) and the mirrored value around center, and take the smaller one.
// The palindrome centered at i must be at least that long.
table[i] = min(maxRight - i, table[center * 2 - i])
}
// Expand around i while the mirrored characters match.
while (charArray[i + table[i] + 1] == charArray[i - table[i] - 1]) {
table[i]++
}
// If this palindrome extends past maxRight, update center and maxRight.
if (i + table[i] > maxRight) {
center = i
maxRight = i + table[i]
}
// Track the longest palindrome found so far.
if (table[i] > maxLength) {
start = (i - table[i] - 1) / 2
maxLength = table[i]
}
}
return str.substring(start, start + maxLength)
}
You can find the code sample on GitHub.
Practice Problems
LeetCode 5. Longest Palindromic Substring
Find the longest palindromic substring. A good problem to practice Manacher’s algorithm.
LeetCode 647. Palindromic Substrings
Count all palindromic substrings in a string. A good problem to practice applying Manacher’s algorithm.
